import java.util.*;

/**
 * Unordered set which can store duplicate elements.
 */
public class MultiSet<E> implements Set<E>
{
    /**
     * Store number of occurrences of each element.
     */
    protected HashMap<E, Integer> data = new HashMap<E, Integer>();

    public int count(E element)
    {
        Integer numOfOccurrences = data.get(element);
        if (numOfOccurrences == null)
            return 0;
        else
            return numOfOccurrences;
    }

    /**
     * Number of distinct elements.
     */
    public int size()
    {
        return data.size();
    }

    public boolean isEmpty()
    {
        return data.isEmpty();
    }

    public boolean contains(Object o)
    {
        return data.containsKey(o);
    }

    public Iterator<E> iterator()
    {
        return data.keySet().iterator();
    }

    public Object[] toArray()
    {
        return data.keySet().toArray();
    }

    public <T> T[] toArray(T[] a)
    {
        return data.keySet().toArray(a);
    }

    /**
     * Add occurrence of element.
     */
    public boolean add(E e)
    {
        Integer numOfOccurrences = data.get(e);
        if (numOfOccurrences == null)
            data.put(e, 1);
        else
            data.put(e, numOfOccurrences + 1);
        // always report successful addition
        return true;
    }

    /**
     * Remove all occurrences of element.
     */
    public boolean remove(Object o)
    {
        Integer numOfOccurrences = data.remove(o);
        return numOfOccurrences != null;
    }

    public boolean containsAll(Collection<?> c)
    {
        return data.keySet().containsAll(c);
    }

    public boolean addAll(Collection<? extends E> c)
    {
        for (E element : c)
            add(element);
        return true;
    }

    public boolean retainAll(Collection<?> c)
    {
        return data.keySet().retainAll(c);
    }

    public boolean removeAll(Collection<?> c)
    {
        return data.keySet().removeAll(c);
    }

    public void clear()
    {
        data.clear();
    }

    /**
     * Copy all elements which occurs at least 'minCount' times to 'destination' collection.
     */
    public void filterOutUnique(Collection<E> destination, int minCount)
    {
          for (E element : this)
              if (count(element) >= minCount)
                  destination.add(element);
    }

    /**
     * Testing routine.
     */
    public static void main(String[] argv) throws Throwable
    {
        MultiSet<String> multiSet = new MultiSet<String>();
        for (int i = 0; i < 10; i++)
            multiSet.add("a");
        assert multiSet.contains("a") && multiSet.count("a") == 10;
        multiSet.remove("a");
        assert !multiSet.contains("a") && multiSet.count("a") == 0;
    }
}
